package 动态链表;

import 动态数组.线性表.List;

import java.util.Comparator;
import java.util.Iterator;

/**
 * 单向循环链表
 * @param <E>
 */
public class LinkedSinglyCircularList<E> implements List<E> {
    //链表的节点对象
    private class Node{
        E data;
        Node next;

        public Node(){
            this(null,null);
        }

        public Node(E data){
            this(data,null);
        }

        public Node(E data, Node next){
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
    //链表的头节点
    private Node head;
    //链表的尾结点
    private Node tail;
    //链表存储的数据个数
    private int size;

    //链表的初始化
    public LinkedSinglyCircularList(){
        head = null;
        tail = null;
        size = 0;
    }

    public LinkedSinglyCircularList(E[] arr){
        for (E e : arr) {
            add(e);
        }
    }


    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size){
            throw new IllegalArgumentException("add index out of range");
        }
        Node node = new Node(element);
        //链表为空直接头尾节点指向该新节点
        if (isEmpty()){
            head = node;
            tail = node;
            tail.next = head;  //new code
            //头节点的添加
        }else if (index == 0){
            node.next = head;
            head = node;
            tail.next = head; //new code
            //尾结点的添加
        }else if (index == size){
            node.next = tail.next; //new code
            tail.next = node;
            tail = node;
            //中间节点的添加，先找该节点的前一个节点
        }else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            node.next = p.next;
            p.next = node;
        }
        size++;
    }

    @Override
    public void remove(E element) {
        //找到要移除元素的角标
        int index = indexOf(element);
        if (index != -1){
            //找到了接直接删除
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("remove index out of range");
        }
        //存储删除前的元素的值
        E ret = null;
        //只用一个元素就直接删除该元素
        if (size == 1){
            ret = head.data;;
            head = null;
            tail = null;
            //删除头节点
        }else if (index == 0){
            //先让一个新节点指向头节点，在断节点直接的联系
            Node del = head;
            ret = del.data;
            head = del.next;
            del.next = null;
            tail.next = head;  // new code
            //删除尾节点，找到尾结点之前的元素
        }else if (index == size - 1){
            Node p = head;
            while (p.next != tail){
                p = p.next;
            }
            ret = tail.data;
            p.next = head; // change code
            tail = p;
            //删除中间
        }else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            Node n = p.next;
            ret = n.data;
            p.next = n.next;
            n.next = null;
        }
        size--;
        return ret;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get index out of the range");
        }
        //返回角标0
        if (index == 0){
            return head.data;
        }else if (index == size - 1){
            return tail.data;
        }else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            return p.data;
        }
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get index out of the range");
        }
        //返回角标0
        E ret = null;
        if (index == 0){
            ret = head.data;
            head.data = element;
        }else if (index == size - 1){
            ret = tail.data;
            tail.data = element;
        }else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            ret = p.data;
            p.data = element;
        }
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int indexOf(E element) {
        Node p = head;
        int index = 0;
        while (!p.data.equals(element)){
            p = p.next;
            index++;
            if (p == head){// change code
                return -1;
            }
        }
        return index;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && head == null && tail == null;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if (isEmpty()){
            sb.append(']');
        }else {
            Node node = head;
            while (true){
                sb.append(node.data);
                if (node == tail){
                    sb.append(']');
                    break;
                }else {
                    sb.append(',');
                }
                node = node.next;
            }
        }
        return sb.toString();
    }

    @Override
    public void sort(Comparator<E> c) {
        if (c == null){
            throw new IllegalArgumentException("comparator can not be null");
        }
        Node nodeA = head;
        Node nodeB = nodeA.next;
        while (true) {
            while (true) {
                if (c.compare(nodeA.data,nodeB.data) > 0) {
                    E e = nodeA.data;
                    nodeA.data = nodeB.data;
                    nodeB.data = e;
                }
                nodeB = nodeB.next;
                if (nodeB == head) { // change code
                    break;
                }
            }
            if (nodeA.next == tail) {
                break;
            }
            nodeA = nodeA.next;
            nodeB = nodeA.next;
        }

    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex){
            throw new IllegalArgumentException("index was error");
        }
        LinkedSinglyList<E> newList = new LinkedSinglyList<>();
        //定义到fromIndex的节点
        Node nodeA = head;
        for (int i = 0; i < fromIndex; i++) {
            nodeA = nodeA.next;
        }
        //定义到toIndex的节点
        Node nodeB = head;
        for (int i = 0; i < toIndex; i++) {
            nodeB = nodeB.next;
        }
        Node p = nodeA;
        while (p != nodeB){
            newList.add(p.data);
            p = p.next;
        }
        return newList;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedSingleListIterator();
    }

    class LinkedSingleListIterator implements Iterator<E>{
        private Node cur = head;
        private boolean flag = true; //表示是否为第一圈

        @Override
        public boolean hasNext() {
            return flag;
        }

        @Override
        public E next() {
            E ret = cur.data;
            cur = cur.next;
            if (cur == head){
                flag = false;
            }
            return ret;
        }
    }

    public void josephusLoop(){
        if (size <= 2){
            return;
        }
        Node p = head;
        while (size != 2){
            p = p.next;
            //删除节点的分类讨论
            //删除头节点往后移，删除未节点向前移，删除操作相同
            Node del = p.next;
            if (del == head){
                head = head.next;
            }else if (del == tail){
                tail = p;
            }
            p.next = del.next;
            del.next = null;
            size--;
            p = p.next;
        }
    }
}
